struct Solution;

#[derive(Clone)]
struct Dp {
    len: usize,
    prev: Option<usize>,
}

impl Solution {
    pub fn get_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
        let n = groups.len();

        let mut dp: Vec<Dp> = Vec::new();
        let mut maxi: Option<Dp> = None;

        for i in 0..n {
            let mut dpi = Dp { len: 0, prev: None };

            for (j, dpj) in dp.iter().enumerate() {
                if groups[i] != groups[j] && dpj.len + 1 > dpi.len {
                    dpi.len = dpj.len + 1;
                    dpi.prev = Some(j);
                }
            }

            if maxi
                .as_ref()
                .map(|maxi| dpi.len > maxi.len)
                .unwrap_or(true)
            {
                maxi = Some(dpi.clone());
            }

            dp.push(dpi);
        }

        let mut now = maxi.map(|maxi| maxi.len);
        let mut path = Vec::new();

        while let Some(nowi) = now {
            path.push(nowi);
            now = dp[nowi].prev;
        }

        path.reverse();

        let mut results = vec![];
        for p in path {
            results.push(words[p].to_string());
        }

        results
    }
}

fn main() {
    let words = vec![
        "a".to_string(),
        "b".to_string(),
        "c".to_string(),
        "d".to_string(),
    ];
    let groups = vec![1, 0, 1, 1];

    dbg!(Solution::get_longest_subsequence(words, groups));
}
